import java.awt.Color;

import javax.swing.JPanel;


@SuppressWarnings("serial")
public class ArvoreAVL	extends JPanel {
	
	Node root;
	final int DELTA = 300;
	public int painelWidth; 
	
	//construtor
	public ArvoreAVL(int n) {
		//Cor do BackGround
		setBackground(Color.WHITE);
		// seta o Layout da Classe
		setLayout(null);	
		// :::::::Arvore:::::::::
		root = null;
		painelWidth = n; // recebe o tamanho do painel arvores.
	}
	
	//função altura
	public int Altura(Node aux) {
		if(aux == null)
			return -1;
		int h_esquerda = 0;
		int h_direita = 0;
		if(aux.esquerdo == null && aux.direito == null)
			return 0;
		h_esquerda = Altura(aux.esquerdo);
		h_direita = Altura(aux.direito);
		
		if(h_esquerda > h_direita)
			return h_esquerda + 1;
		else
			return h_direita + 1;
	}
	/********************************************************************************************************
	 **************************************FUNÇÕES DE ROTAÇÃO************************************************
	 ********************************************************************************************************/
	public void RotacaoSimplesDireita (Node aux) {
		Node novo_pai = aux.esquerdo;
		Node pai_vitima = aux.pai;
		
		if(aux == root) {
			aux.esquerdo = novo_pai.direito;
			if(aux.esquerdo != null)
				aux.esquerdo.pai = aux; // ajusta o pai de auz esquerdo
			
			novo_pai.direito = aux;
			aux.pai = novo_pai;
			root = novo_pai;
			novo_pai.pai = null;
			return;
		}
		if (aux == pai_vitima.esquerdo) {
			
			aux.esquerdo = novo_pai.direito;
			if(aux.esquerdo != null)
				aux.esquerdo.pai = aux; // ajusta o pai de auz esquerdo
			
			novo_pai.direito = aux;
			aux.pai = novo_pai;
			
			novo_pai.pai = pai_vitima;
			
			novo_pai.pai.esquerdo = novo_pai;
		} else if (aux == pai_vitima.direito) {
			aux.esquerdo = novo_pai.direito;
			if(aux.esquerdo != null)
				aux.esquerdo.pai = aux; // ajusta o pai de auz esquerdo
			
			novo_pai.direito = aux;
			aux.pai = novo_pai;
			
			novo_pai.pai = pai_vitima;
			
			novo_pai.pai.direito = novo_pai;
		}
		
	} //RotacaoSimplesDireita
	
	public void RotacaoSimplesEsquerda(Node aux) {
		Node novo_pai = aux.direito;
		Node pai_vitima = aux.pai;
		
		if(aux == root) {
			aux.direito = novo_pai.esquerdo;
			if(aux.direito != null)
				aux.direito.pai = aux; // ajusta o pai de auz esquerdo
			
			novo_pai.esquerdo = aux;
			aux.pai = novo_pai;
			root = novo_pai;
			novo_pai.pai = null;
			return;
		}
		if (aux == pai_vitima.esquerdo) {
			
			aux.direito = novo_pai.esquerdo;
			if(aux.direito != null)
				aux.direito.pai = aux; // ajusta o pai de auz esquerdo
			
			novo_pai.esquerdo = aux;
			aux.pai = novo_pai;
			
			novo_pai.pai = pai_vitima;
			
			novo_pai.pai.esquerdo = novo_pai;
		} else if (aux == pai_vitima.direito) {
			aux.direito = novo_pai.esquerdo;
			if(aux.direito != null)
				aux.direito.pai = aux; // ajusta o pai de auz esquerdo
			
			novo_pai.esquerdo = aux;
			aux.pai = novo_pai;
			
			novo_pai.pai = pai_vitima;
			
			novo_pai.pai.direito = novo_pai;
		}
	} // RotacaoSimplesEsquerda
	
	public void RotacaoDupla_esq_dir (Node aux) {
		RotacaoSimplesEsquerda(aux.esquerdo);
		RotacaoSimplesDireita(aux);
	} // RotacaoDupla_esq_dir
	
	public void RotacaoDupla_dir_esq (Node aux) {
		RotacaoSimplesDireita(aux.direito);
		RotacaoSimplesEsquerda(aux);
	} // RotacaoDupla_dir_esq
	
	public boolean Is_Balanced (Node aux) {
		if (aux == null)
			return true;
		boolean balanced = true;
		int fb = Altura (aux.esquerdo) - Altura (aux.direito);
		if (fb > 1 || fb < -1 || Is_Balanced(aux.esquerdo) == false || Is_Balanced(aux.direito) == false)
			balanced = false;
		return balanced;
	} 
	
	public void Balanceia (Node aux) {
		if(aux == null)
			return;
		if (aux.esquerdo != null)
			Balanceia (aux.esquerdo);
		if (aux.direito != null);
			Balanceia (aux.direito);
		
		int fb = Altura (aux.esquerdo) - Altura (aux.direito);
		
		if (fb > 1) {
			if(Altura (aux.esquerdo.esquerdo) - Altura (aux.esquerdo.direito) < 0)
				RotacaoDupla_esq_dir (aux);
			else
				RotacaoSimplesDireita(aux);
		}
		if (fb < -1)
			if(Altura (aux.direito.esquerdo) - Altura (aux.direito.direito) > 0)
				RotacaoDupla_dir_esq (aux);
			else
				RotacaoSimplesEsquerda (aux);
	} // Balanceia
	
	/********************************************************************************************************
	 ************************************** FUNÇÃO VAZIA ****************************************************
	 ********************************************************************************************************/
	public boolean vazia () { return root == null; }
	
	/********************************************************************************************************
	 ************************************* FUNÇÕES DE INSERÇÃO **********************************************
	 ********************************************************************************************************/
	public void InserirAPartirDaRaiz (int n) {
		Inserir(n, 0, 0, DELTA, null, root);
		Balanceia(root);
		Reposicione((painelWidth/2) - root.getWidth()/2, 30, DELTA, root);
	}
	// :::::::::::::::::::Função Inserir::::::::::::::::::::
	public void Inserir(int n,int posx, int posy, int delta, Node novo, Node aux) {
		
		if(aux != null) // Não permite que se coloque número ja contidos na arvore
			if(aux.getNumero() == n)
				return;
		
		if(delta < 15)	// limita o delta a fica maior que 18
			delta = 15;
		if (novo == null) {
			novo = new Node(n);
		}
		if(vazia()) {
			root = novo;
			root.setPosition ((painelWidth/2) - root.getWidth()/2, 30);
			root.pai = null;
			this.add(root);
			return;
		}
		boolean
			cond1 = (aux.getNumero() < n && aux.direito == null ),
			cond2 = (aux.getNumero() < n && aux.direito != null),
			cond3 = (aux.getNumero() > n && aux.esquerdo == null);
		
		if(cond1) {
			aux.direito = novo;
			(aux.direito).pai = aux;
			(aux.direito).setPosition(aux.x + delta, aux.y + 60);
			this.add(aux.direito);	
			// Inserir Linha.
			aux.l_direita = new Linha(aux.x, aux.y, aux.direito.x, aux.direito.y, false);
			add(aux.l_direita);
		}
		else if(cond2) {
			Inserir(n, aux.x, aux.y, (6*delta)/11 , novo, aux.direito);
		}else if(cond3) {
			aux.esquerdo = novo;
			aux.esquerdo.pai = aux;
			aux.esquerdo.setPosition (aux.x - delta, aux.y + 60);
			this.add(aux.esquerdo);
			//Insere linha
			aux.l_esquerda = new Linha(aux.x, aux.y, aux.esquerdo.x, aux.esquerdo.y, true);
			add(aux.l_esquerda);
		
		}else {
			Inserir(n, aux.x, aux.y, (6*delta)/11, novo, aux.esquerdo);
		}
		
	} // Inserir
	/********************************************************************************************************
	 **************************************FUNÇÃO DE REPOSICIONAMENTO****************************************
	 ********************************************************************************************************/
	public void Reposicione(int x, int y, int delta, Node aux) {
		remove(aux);
		aux.setPosition(x, y);
		add(aux);	
		//Recursão
		if (aux.direito != null)
			Reposicione (aux.x + delta, aux.y + 60, (6*delta)/11, aux.direito);
		if (aux.esquerdo != null)
			Reposicione (aux.x - delta, aux.y + 60, (6*delta)/11, aux.esquerdo);
		
		//Trabalho com linhas
		if(aux.l_direita != null)
			remove(aux.l_direita);
		if(aux.l_esquerda != null)
			remove(aux.l_esquerda);
		if(aux.direito != null){
			aux.l_direita = new Linha(aux.x, aux.y, aux.direito.x, aux.direito.y, false);
			add(aux.l_direita);
		}
		if(aux.esquerdo != null){
			aux.l_esquerda = new Linha(aux.x, aux.y, aux.esquerdo.x, aux.esquerdo.y, true);
			add(aux.l_esquerda);
		}
	}
	
	/********************************************************************************************************
	 **************************************FUNÇÕES DE BUSCA**************************************************
	 ********************************************************************************************************/
	
	public Node Busca (int n, Node aux) {
		
		if(n == aux.getNumero())
			return aux;
		else if(n > aux.getNumero() && aux.direito != null)
			return Busca(n, aux.direito);
		else if(n < aux.getNumero() && aux.esquerdo != null)
			return Busca(n, aux.esquerdo);
		return null;
	}
	
	/********************************************************************************************************
	 **************************************FUNÇÕES DE REMOÇÃO************************************************
	 ********************************************************************************************************/
	
	public void Remover (int n) {
		Node aux = Busca (n, root);
		
		if (aux == null)
			return;
		
		//Caso Especial - Raiz -
		if (aux == root) {
			if (aux.esquerdo == null && aux.direito == null) {
				remove(root);
				root = null;
			}
			else if(Altura(aux.direito) >= Altura(aux.esquerdo)) {
				root = aux.direito;
				aux.direito.pai = null;
				
				// Procura um lugar vazio a esquerda de aux.esquerdo.
				Node aux2 = aux.direito;
				if(aux.esquerdo != null){
					while (aux2.esquerdo != null)
						aux2 = aux2.esquerdo;
					
					aux2.esquerdo = aux.esquerdo;
					aux2.esquerdo.pai = aux2;
					
					
				}	
				Reposicione(aux.x, aux.y, DELTA, aux.direito);
			}else if(Altura(aux.esquerdo) > Altura(aux.direito)) {
				root = aux.esquerdo;
				aux.esquerdo.pai = null;
				
				// Procura um lugar vazio a direita de aux.direito
				if(aux.direito != null ) {
					Node aux2 = aux.esquerdo;
					while (aux2.direito != null)
						aux2 = aux2.direito;
					
					aux2.direito = aux.direito;
					aux2.direito.pai = aux2;
				}
				
			}
			remove(aux);
			if(aux.l_direita != null)
				remove(aux.l_direita);
			if(aux.l_esquerda != null)
				remove(aux.l_esquerda);
			
			
			
			
		} else {
		// ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
		// :::::::::::::::: Caso o Elemento a ser Removido não seja root:::::::::::::
		// ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
			int delta = aux.pai.x - aux.x; // distancia horizontal entre o pai do elemento a ser removido e ele.
			if(delta < 0) // distancia nao pode ser negativo.
				delta = -delta;
			
			// Caso ele esteja a direita do pai dele
			if(aux.pai.direito == aux) {	
				
				if (aux.esquerdo == null && aux.direito == null) {
					aux.pai.direito = null;
				}
				else if(Altura(aux.esquerdo) <= Altura(aux.direito)) {
					aux.pai.direito = aux.direito;
					aux.direito.pai = aux.pai;
					
					// Procura um lugar vazio a esquerda de aux.esquerdo.
					Node aux2 = aux.direito;
					if(aux.esquerdo != null){
						while (aux2.esquerdo != null)
							aux2 = aux2.esquerdo;
						aux2.esquerdo = aux.esquerdo;
						aux2.esquerdo.pai = aux2;
					}				
				}else{
					aux.pai.direito = aux.esquerdo;
					aux.esquerdo.pai = aux.pai;
					
					// Procura um lugar vazio a direita de aux.direito
					if(aux.direito != null ) {
						Node aux2 = aux.esquerdo;
						while (aux2.direito != null)
							aux2 = aux2.direito;
						aux2.direito = aux.direito;
						aux2.direito.pai = aux2;
					}
				}
			}
			// Caso o elemento a ser removido seja Filho esquerdo do pai dele!
			else {
				if (aux.esquerdo == null && aux.direito == null) {
					aux.pai.esquerdo = null;
				}
				// Se a Altura do filho direito do elemento for
				// maior que a do esquerdo o elemento direito ficará
				// no lugar do elemento a ser removido
				else if(Altura(aux.esquerdo) <= Altura(aux.direito)) {
					aux.pai.esquerdo = aux.direito;
					aux.direito.pai = aux.pai;
					
					// Procura um lugar vazio a esquerda de aux.esquerdo.
					Node aux2 = aux.direito;
					if(aux.esquerdo != null){
						while (aux2.esquerdo != null)
							aux2 = aux2.esquerdo;
						aux2.esquerdo = aux.esquerdo;
						aux2.esquerdo.pai = aux2;
					}	
					
				}
				// Se for o contrário
				// o elemento esquerdo ficara no lugar
				// do elemento a ser removido
				else {
					aux.pai.esquerdo = aux.esquerdo;
					aux.esquerdo.pai = aux.pai;
					
					// Procura um lugar vazio a direita de aux.direito
					if(aux.direito != null ) {
						Node aux2 = aux.esquerdo;
						while (aux2.direito != null)
							aux2 = aux2.direito;
						aux2.direito = aux.direito;
						aux2.direito.pai = aux2;
					}
				}
			}
		}
		//Faz balanceamento
		while (!Is_Balanced (root))
			Balanceia (root);
		// Remove Elemento da interface
		if (root != null) {
			remove(aux);
			//removendo linhas
			if(aux.l_direita != null)
				remove(aux.l_direita);
			if(aux.l_esquerda != null)
				remove(aux.l_esquerda);
		// Faz o reposicionamento dos elementos
		Reposicione((painelWidth/2) - root.getWidth()/2, 30, DELTA, root);
		}
	} // Remover

}	
	

